U.S. Pat. Nos. 6,963,800 (“Routing soldiers around enemy attacks and battlefield obstructions”) and 7,756,635 (“Method and System for Generating and Presenting Off-Road Travel Routes”) by Randy Milbert pioneered automated off-road route planning. They enabled soldiers and civilians alike to plan routes through any terrain—desert, jungle, mountainous, urban, or woodland—on- or off-road.
Whereas on-road route planning is limited to a relatively sparse graph—one can only go left, right, or straight at a typical intersection—off-road route planning leads to immensely denser graphs because one has 360 degrees of freedom at every point.
An exemplary embodiment described in U.S. Pat. Nos. 6,963,800 and 7,756,635 uses A* (see pages 93 to 99 of “Artificial Intelligence: A Modern Approach, Third Edition” by Stuart Russell and Peter Norvig) to generate these off-road routes. A*'s computational speed and memory usage are vastly superior to many alternative path finding algorithms such as breadth- and depth-first search, but A* is still unable to quickly generate high-quality, long off-road routes on resource-constrained platforms such as mobile phones and personal navigation devices (PNDs).
Memory-bounded variants of A* (see pages 101 to 102 of “Artificial Intelligence: A Modern Approach, Third Edition”) such as simplified memory-bounded A* (SMA*) reduce memory consumption and maintain optimality given an admissible heuristic, but they sacrifice performance. All nodes explored by A* are also explored by SMA*, it is just that some of them may be temporarily removed from memory on resource-constrained platforms.
Anytime variants of A* such as Anytime Repairing A* (ARA*) (see “ARA*: Anytime A* with Provable Bounds on Sub-Optimality” by Maxim Likhachev, Geoff Gordon, and Sebastian Thrun) also reduce memory consumption and maintain optimality given an admissible heuristic, but they too sacrifice performance if allowed to run to completion. In that case, ARA* explores at least as many nodes as A*. Its benefit is that it enables one to obtain suboptimal routes with bounded errors while route generation progresses.
Another approach (see “An optimal pathfinder for vehicles in real-world digital terrain maps” by F. Markus Jönsson) creates a sub-sampled version of the graph, generates a coarse route, divides the coarse route into segments, generates fine routes using the segment end points, and then stitches the fine routes together. Again, this solution reduces memory consumption. In some cases, it also reduces computation time because it is quicker to generate several short route segments rather than one long complete route. This approach has a significant disadvantage, however, in that it produces routes with tie points where the fine routes were drawn to coarse segment end points, which may be in undesirable terrain.
None of these existing solutions is capable of quickly generating high-quality, long off-road routes on resource-constrained platforms.